package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 二分查找算法实现
 * 
 * @ClassName: Erfenchaozhao
 * @Auther: csy
 * @Date: 2020/4/5 14:11
 * @Description: 实现了经典的二分查找算法，用于在有序数组中高效查找目标元素
 * 
 * 算法思想：
 * 1. 二分查找是一种高效的查找算法，要求数组必须是有序的
 * 2. 每次将查找区间一分为二，与中间元素比较，缩小查找范围
 * 3. 时间复杂度为O(log n)，远优于线性查找的O(n)
 * 
 * 适用场景：
 * 1. 在大规模有序数据集中查找特定元素
 * 2. 需要高效查找且数据量较大的情况
 * 3. 数据集能够支持随机访问（如数组）
 */
public class Erfenchaozhao {
    
    /**
     * 示例有序数组，用于测试二分查找算法
     * 数组必须是有序的（升序或降序），这里使用升序数组
     */
    static int[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    /**
     * 二分查找算法实现
     * 
     * 算法步骤：
     * 1. 初始化查找区间为整个数组范围
     * 2. 计算中间位置，将数组分为两部分
     * 3. 比较中间元素与目标值：
     *    - 如果相等，则找到目标，返回索引
     *    - 如果目标值小于中间元素，在左半部分继续查找
     *    - 如果目标值大于中间元素，在右半部分继续查找
     * 4. 重复步骤2-3，直到找到目标或查找区间为空
     * 
     * 举例说明：
     * 在数组[1,2,3,4,5,6,7,8,9]中查找元素7
     * 1. 初始状态：start=0, end=8, middle=4, a[middle]=5
     * 2. 7 > 5，在右半部分查找：start=5, end=8
     * 3. middle=6, a[middle]=7，找到目标，返回索引6
     *
     * @param a   有序数组（假设为升序）
     * @param key 要查找的目标值
     * @return 目标值在数组中的索引，如果未找到则返回-1
     */
    public static int search(int[] a, int key) {
        // 初始化索引为-1，表示未找到目标值
        int index = -1;
        // 初始化查找区间的起始位置
        int start = 0;
        // 初始化查找区间的结束位置（注意：这里应该是a.length-1而不是a.length）
        int end = a.length - 1;
        
        // 当查找区间有效时继续查找
        while (start <= end) {
            // 计算中间位置（注意：这种计算方式在数组很大时可能导致整数溢出）
            // 更安全的写法是：int middle = start + (end - start) / 2;
            int middle = start + (end - start) / 2;
            
            // 比较中间元素与目标值
            if (key < a[middle]) {
                // 目标值小于中间元素，在左半部分查找
                end = middle - 1;
            } else if (key > a[middle]) {
                // 目标值大于中间元素，在右半部分查找
                start = middle + 1;
            } else {
                // 找到目标值，返回其索引
                return middle;
            }
        }
        
        // 未找到目标值，返回-1
        return index;
    }

    /**
     * 主方法：用于测试二分查找算法
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：在有序数组中查找存在的元素
        int target1 = 7;
        int result1 = search(a, target1);
        System.out.println("测试用例1：");
        System.out.println("数组：" + Arrays.toString(a));
        System.out.println("查找元素：" + target1);
        if (result1 != -1) {
            System.out.println("查找成功！元素" + target1 + "在数组中的索引为：" + result1);
        } else {
            System.out.println("查找失败！元素" + target1 + "不在数组中");
        }
        
        // 测试用例2：在有序数组中查找不存在的元素
        int target2 = 10;
        int result2 = search(a, target2);
        System.out.println("\n测试用例2：");
        System.out.println("数组：" + Arrays.toString(a));
        System.out.println("查找元素：" + target2);
        if (result2 != -1) {
            System.out.println("查找成功！元素" + target2 + "在数组中的索引为：" + result2);
        } else {
            System.out.println("查找失败！元素" + target2 + "不在数组中");
        }
        
        // 测试用例3：在空数组中查找元素（边界情况）
        int[] emptyArray = {};
        int target3 = 5;
        int result3 = search(emptyArray, target3);
        System.out.println("\n测试用例3：");
        System.out.println("数组：" + Arrays.toString(emptyArray));
        System.out.println("查找元素：" + target3);
        if (result3 != -1) {
            System.out.println("查找成功！元素" + target3 + "在数组中的索引为：" + result3);
        } else {
            System.out.println("查找失败！元素" + target3 + "不在数组中");
        }
    }
}
